class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }
    	int n = s1.length();
		int m = s2.length();
		vector<vector<int> > dp(n + 1, vector<int>(m + 1));
		Recursive(dp, s1, s2, s3, 0, 0, 0);
		return dp[0][0] == 1;
    }

	int Recursive(vector<vector<int> >& dp,
		const string& s1,
		const string& s2,
		const string& s3,
		int i,
		int j,
		int k) {
		if (dp[i][j]) {
			return dp[i][j];
		}
		if (i == s1.length() && j == s2.length()) {
			dp[i][j] = 1;
			return 1;
		}
		if (i < s1.length() && s3[k] == s1[i]) {
			if (Recursive(dp, s1, s2, s3, i + 1, j, k + 1) == 1) {
				dp[i][j] = 1;
				return 1;
			}
		}
		if (j < s2.length() && s3[k] == s2[j]) {
			if (Recursive(dp, s1, s2, s3, i, j + 1, k + 1) == 1) {
				dp[i][j] = 1;
				return 1;
			}
		}
		dp[i][j] = -1;
		return -1;
	}

};